In an effort to increase I/O bandwidth in high performance processor based systems, a number of companies have developed the HyperTransport (“HT”) I/O interconnect structure. Briefly, the HT I/O interconnect structure is a scalable device level architecture that provides a significant increase in transaction throughput over existing I/O bus architectures such as Peripheral Component Interconnect (“PCI”) and Advanced Graphics Port (“AGP”).
The foundation of the HT I/O interconnect is dual point-to-point unidirectional links consisting of a data path, control signals, and clock signals. The HT I/O interconnect can provide both point-to-point links and a scalable network topology using HT I/O switching fabrics. Thus, an HT based system can be expanded using HT switches to support multilevel, highly complex systems.
Communications between multiple HT I/O devices are known as data streams. Each data stream contains one or more packets of information. Each packet of information contains a packet ID and a data payload. The packet ID is also commonly referred to as a unit ID. Because all packets are transferred to or from a host bridge, the packet ID provides information that can be utilized to determine the source or destination of the packet. A more detailed description of the HT I/O interconnect structure is presented in Appendix A.
FIG. 1 presents an HT I/O device 100 that interfaces with a first unidirectional link 110 and a second unidirectional link 120. Thus, the HT I/O device 100 can receive input data streams and transmit output data streams via unidirectional links 110 and 120. The HT I/O device 100 contains input ports 130 and 150 for receiving data streams and output ports 140 and 160 for transmitting data streams. The HT device 100 may also contain circuitry for generating packets that can be transmitted as output data streams via the output ports 140 and 160.
HT I/O devices may also be daisy chained as shown in FIG. 2. FIG. 2 presents a portion of a single unidirectional link in an HT I/O interconnect. The unidirectional link shown contains three HT I/O devices 210, 220, and 230. If the first HT I/O device 210 receives a data stream with a destination ID that is equal to the ID of the first HT I/O device 210, then the first HT I/O device 210 will receive and internally process the data stream. However, if the destination ID is not equal to the ID of the first HT I/O device 210, then the first HT I/O device 210 will forward the data stream to the second HT I/O device 220.
As the first HT I/O device 210 may also have the capability to generate packets, the output data stream of the first HT I/O device 210 is a composite of the input packet stream received by the first HT I/O device 210 and the internally generated packets. These internally generated packets will be referred to as an internal data stream.
The data stream received by the first HT I/O device 210 and the device's internal data stream may vary with time. For example, the input data stream for the first HT I/O device 210 may contain no packets over a given time interval. Thus, all packets in the internal data stream generated during that time interval by the first HT I/O device 210 may be transmitted through the first HT I/O device's output port. Alternately, if the data stream received by the first HT I/O device 210 and the device's internal data stream both contain a large number of packets, the HT I/O device may be required to choose between forwarding the received data stream or outputting the internally generated packets. The process by which such a choice is made is known in the art as a forwarding fairness algorithm.
Prior art systems allow an HT I/O device to insert internally generated packets into an output data stream freely if the output data stream is empty. However, if the output data stream contains a large number of packets, the prior art systems only allow the HT I/O device to insert internally generated packets into the output data stream at a rate that is not greater than the rate that the HT I/O device is receiving and forwarding packets from another HT I/O device. Such prior art systems are not optimal. Thus, a more optimal method of merging two data streams into a single data stream is needed.